import java.util.HashMap;
import java.util.Map;

public class Solution1074 {
    public int numSubmatrixSumTarget(int[][] matrix, int target) {
        int m=matrix.length,n=matrix[0].length;
        int[][] f=new int[m+1][n+1];
        for (int i=1;i<=m;i++){
            for (int j=1;j<=n;j++){
                f[i][j]=f[i][j-1]+f[i-1][j]+matrix[i-1][j-1]-f[i-1][j-1];
            }
        }
        int ans=0;
        Map<Integer,Integer>[][] maps=new HashMap[m+1][m+1];
        for (int b=1;b<=n;b++){
            for (int a=1;a<=m;a++) {
                for (int c=0;c<a;c++) {
                    if (maps[a][c]==null){
                        maps[a][c]=new HashMap<>();
                    }
                    maps[a][c].put(f[a][b-1]-f[c][b-1],maps[a][c].getOrDefault(f[a][b-1]-f[c][b-1],0)+1);
                }
            }
            for (int a=1;a<=m;a++){
                for (int c=0;c<a;c++){
                    ans=ans+maps[a][c].getOrDefault(f[a][b]-f[c][b]-target,0);
                }
            }
        }
        return ans;
    }

    public static void main(String[] args) {
        System.out.println(new Solution1074().numSubmatrixSumTarget(new int[][]{{0,1,0},{1,1,1},{0,1,0}},0));
    }
}
